export function combine(n: number, k: number): number[][] {
    const ret: number[][] = [];
    let j = 1;
    while (j <= n) {
        const path: number[] = [];
        backTrace(j, n, k, path, ret);
        j++;
    }
    return ret;
};

function backTrace (j: number, n: number, k: number, path: number[], ret: number[][]) {
    path.push(j);
    // 组合中的第 i 个数
    const i = path.length;
    // 不算j，还需要 needCount 个数
    const needCount = k - i;
    // j 后面还有 hasCount 个数
    const hasCound = n - j;

    if (path.length === k) {
        ret.push([...path]);
        return;
    }
    if (needCount > hasCound) return;

    for (let m = j+1; m <= n; m++) {
        backTrace(m, n, k, path, ret);
        path.pop();
    }
}